//============================================================================
// Name        : ms001.cpp
// Author      : Tadas
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#define EPS 1.0E-5
#define JMAX 30
#define K 5

#include <iostream>
#include <math.h>

using namespace std;

void intPol(double xa[], double ya[], int n, double x, double &y, double &dy){

    int i, m, ns = 0;

    double den, dif, dift, hd, hu, w, *u, *d;

    u = new double[n];
    d = new double[n];

    //assert(u != NULL && d != NULL);
    dif = fabs(x - xa[0]);

    for (i = 0; i < n; i++){
        if ((dift = fabs(x - xa[i])) < dif){
            ns = i;
            dif = dift;
        }

        u[i] = ya[i];
        d[i] = ya[i];
    }

    y = ya[ns--];
    cout << "Y0: " << y << endl;
    for (m = 1; m < n; m++){
        for (i = 0; i < n - m; i++){

            hd = xa[i] - x;
            hu = xa[i + m] - x;

            w = d[i + 1] - u[i];
            den = hd - hu;

            if (den == 0)
                break;

            den = w/den;

            d[i] = hd * den;
            u[i] = hu * den;
        }

        if (2*ns < (n - m - 1))
            dy = d[ns + 1];
        else
            dy = u[ns--];
        cout << "dY pokytis " << m << " zingsnyje, nuo nario " << ns+2
             << "(" << y << "): " << dy << endl;
        y += dy;
        cout << "Y" << m << ": " << y << endl;
    }

    delete []u;
    delete []d;
}

int main() {
	double xa[] = {1, 2, 3, 4};
	double ya[] = {0.0, 12, 10, 0};

	double x = 2.2;

	double y = 0;
	double dy = 0;
	int n = 4;

	intPol(xa, ya, n, x, y, dy);
//	cout << "dY: " << dy << endl;
//	cout << "Y: " << y << endl;


	return 0;
}
